/**************************************************************************
*   Copyleft 2009 by        											  *
*	Iwanicki Krzysztof													  *
*   <www.gamma.mini.pw.edu.pl/~iwanickik>		                          *
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
*   This program is distributed in the hope that it will be useful,       *
*   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
*   GNU General Public License for more details.                          *
***************************************************************************/
#ifndef __VPRIORITY_LIST_H__
#define __VPRIORITY_LIST_H__

#include "./vString.h"
#include "./vPair.h"
#include "../MemoryTracker/vMemoryTracker.h"

namespace Vendetta {
	/*! \class Priority list.
	 *	\brief Grows dynamically when it should.
	 */
	template <class TV> class vPriorityList {
	private:

		/*! \class vElement.
		 *	\brief Single list list element.
		 */
		class vElement {
		public:
			/*! \brief Constructor.
			 *
			 *	Initializes key with given key, value with given value
			 *	and links it to list.
			 *
			 *	\param key Key.
			 *	\param value Value.
			 *	\param list List.
			 */
			vElement(const TV &value, const vUInt priority, vElement** list): NextPtr(vNull), Value(value), Priority(priority) {
				NextPtr = *list;
				*list = this;
			}

			/*! \brief Constructor.
			*
			*	Initializes key with given key, value with given value
			*	and links it to list.
			*
			*	\param key Key.
			*	\param value Value.
			*	\param list List.
			*/
			vElement(const TV &value, const vUInt priority, vElement** list, vElement** prev): NextPtr(vNull), 
				Value(value), Priority(priority) {
				if (!list) {
					NextPtr = vNull;
				} else {
					NextPtr = *list;
				}
				(*prev)->NextPtr = this;
			}


		public:
			TV			Value;		//! Value
			vUInt		Priority;	//! Priority
			vElement*	NextPtr;	//! Link to next element on the list
		};

	public:

		/*! \brief Constructor.
		 *	
		 */
		vPriorityList(): mSize(0), mpHead(vNull) { }

		/*! \brief Copying constructor.
		 *
		 *
		 *	\param hashArray other hash array to copy data from.
		 */
		vPriorityList(const vPriorityList &list): mSize(0), mpHead(vNull)	{
			*this = list;
		}

		/*! \brief Destructor.
		 *
		 *	Kills all data.
		 */
		~vPriorityList() {
			Clear();
		}
		
		/*! \brief Assign operator.
		 *
		 *
		 *	\param hashArray Other hash array to assign data from.
		 */
		vPriorityList& operator=(const vPriorityList &list)	{
			if (this != &list) {
				Clear();
				mSize = list.mSize;
				mpHead = vNull;
				vElement* pTemp = list.mpHead, *pPrev = vNull;
				while (pTemp) {
					if (!mpHead) {
						new vElement(pTemp->Value, pTemp->Priority, &mpHead);
						pPrev = mpHead;
					} else {
						new vElement(pTemp->Value, pTemp->Priority, vNull, &pPrev);
						pPrev = pPrev->NextPtr;
					}
					//mSize++;
					pTemp = pTemp->NextPtr;
				}
			}
			
			return *this;
		}
		const vPair<vUInt, TV> Element(vUInt uiIndex) {
			vIterator iter(*this);
			vUInt i = 0;

			while (i < uiIndex && iter) {
				++iter;
				i++;
			}

			if (!iter) {
				throw vFatalException("Index out of bounds.In vPriorityList::Element.");
			} else {
				return vPair<vUInt, TV>(iter.Priority(), iter.Value());
			}
		}

		/*! \brief Returns size of list.
		 *
		 *
		 *	\return Size of list.
		 */
		vUInt Size() const {
			return mSize;
		}

		/*! \brief Empties hash array.
		 */
		vVoid Clear() {
			vElement* tmp = mpHead, *toDel;
			while (tmp) {
				toDel = tmp;
				tmp = tmp->NextPtr;
				vDelete(toDel);
			}
			mSize = 0;
			mpHead = vNull;
		}

		/*! \brief Puts element into list.
		 *
		 *
		 *	\param priority Priority of inserted item.
		 *	\param value Value to be inserted.
		 */
		vVoid Add(const vUInt priority, const TV &value) {
			vElement* tmp = mpHead, *pPrev = vNull;
			
			if (!mpHead) {
				new vElement(value, priority, &mpHead);
				mSize++;
				return;
			}
			while (tmp) {
				if (tmp->Priority > priority) {
					if (!pPrev) {
						new vElement(value, priority, &mpHead);
					} else {
						new vElement(value, priority, &tmp, &pPrev);
					}
					mSize++;
					return;
				}
				pPrev = tmp;
				tmp = tmp->NextPtr;
			}
			if (pPrev) {
				new vElement(value, priority, vNull, &pPrev);
				mSize++;
			}
		}

		/*! \brief Puts element into list.
		*
		*
		*	\param value Pair of priority and value.
		*/
		vPriorityList& operator<<(const vPair<vUInt, TV> value) {
			Add(value.First, value.Second);

			return *this;
		}

		/*! \brief Removes element at with given value and returns its value.
		 *
		 *
		 *	\param value Value to be returned in case of success.
		 *	\return True if element with value existed (that is removal was successful).
		 */
		vBool Remove(TV &value) {
			V_CHECK(mSize > 0);
			
			vElement* tmp = mpHead;
			vElement* prev = vNull;

			while (tmp) {
				if (tmp->Value == value) {
					if (prev) {
						prev->NextPtr = tmp->NextPtr;
					} else {
						mpHead = tmp->NextPtr;
					}
					vDelete(tmp);
					mSize--;

					return true;
				}
				prev = tmp;
				tmp = tmp->NextPtr;
			}

			return false;
		}

		/*! \brief Checks if list is empty.
		*
		*
		*	\return True if there is zero elements, false otherwise.
		*/
		inline vBool IsEmpty() const {
			return !mSize;
		}

		/*! \class Iterator.
		 *	\brief Iterates through list array elements in "random" order.
		 */
		class vIterator {
		public:

			/*! \brief Constructor (the only allowed).
			 *
			 *	Assigns passed list as a set to iterate through
			 *	and starts iteration.
			 *
			 *	\param hashArray Hash array.
			 */
			vIterator(vPriorityList<TV> &list): mQueue(list), mpList(vNull) {
				Start();
			}

			/*! \brief Begins iteration.
			 */
			vVoid Start() {
				if (mQueue.mSize > 0) {
					mpList = mQueue.mpHead;
					return;
				}
				mpList = vNull;
			}

			/*! \brief Moves to next element if possible.
			 */
			vVoid operator ++ () {
				if (mpList) {
					if (mpList = mpList->NextPtr) {
						return;
					}
				}
			}

			/*! \brief Tells whether there's any element at current iterator's position.
			 *
			 *
			 *	\return True if there's, false otherwise.
			 */
			operator vBool() const {
				return mpList != vNull;
			}

			/*! \brief Returns value of current element.
			 *
			 *
			 *	\return Value of current element.
			 */
			TV& Value() const {
				V_CHECK(mpList);

				return mpList->Value;
			}

			/*! \brief Returns priority of current element.
			 *
			 *
			 *	\return Priority of current element.
			 */
			vUInt& Priority() const {
				V_CHECK(mpList);

				return mpList->Priority;
			}

		private:

			vPriorityList<TV>&		mQueue;	//! Iterator's queue array
			vInt					mPos;	//! key into array of lists
			vElement*				mpList; //! Pointer to element on list
		};

		friend class vIterator;



	protected:
		vElement*	mpHead;		//! Array of lists
		vUInt		mSize;		//! Total number of elements on all lists

	};
}

#endif // __VPRIORITY_LIST_H__